#include <iostream>
#include <vector>

#include <cstdlib>
#include <ctime>

using namespace std;

int partition(vector<int>&v, int start, int end) {
	int l = start + 1;
	int r = end;

	//为防止在极端情况下，快速排序退化为冒泡排序
	srand(time(nullptr));
	int t = rand() % (r - l + 1) + l;
	swap(v[start], v[t]);
	
	int pivot = v[start];
	while(l < r) {
		while(l < r && v[l] <= pivot) l++;
		while(l < r && v[r] >= pivot) r--;
		if(l < r) {
			swap(v[l],v[r]);
			l++;
			r--;
		}
	}
	if(l == r && pivot < v[r]) r--;
	swap(v[start], v[r]);
	return r;
}
void QuickSort1(vector<int>& v, int l, int r) {
	if(l >= r)
		return ;
	int middle = partition(v, l, r);
	QuickSort1(v, l, middle - 1);
	QuickSort1(v, middle + 1, r);
}


void QuickSort2(vector<int>& arr, int l, int r) {
	if(l >= r) return;
	int i = l, j =r;

	srand(time(NULL));
    int t = rand()%(r - l + 1) + l;
    swap( arr[l], arr[t]);

	while(i < j) {
		while(i < j && arr[j] >= arr[l]) j--;
		while(i < j && arr[i] <= arr[l]) i++;
		swap(arr[i], arr[j]);
	}
	swap(arr[i], arr[l]);
	QuickSort2(arr, l, i-1);
	QuickSort2(arr, i+1, r);
}

int main() {
	vector<int> v{1,4,3,2,7,9,5,10,6,3};
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	QuickSort1(v, 0, v.size()-1);
	//QuickSort2(v, 0, v.size()-1);
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	return 0;
}
/*
平均（最优）时间复杂度为 O(nlogn)，最坏的时间复杂度为 O(n^2);
空间复杂度与递归的层数有关，每层递归会生成一些临时变量，所以空间复杂度为 O(logn) ~ O(n);
平均空间复杂度为 O(logn)。
*/

